- Title
- Minimum weight resolving sets of grid graphs
- Creator
- Andersen, Patrick; Grigorious, Cyriac; Miller, Mirka
- Relation
- Discrete Mathematics, Algorithms and Applications Vol. 8, Issue 3, no. 1650048
- Publisher Link
- http://dx.doi.org/10.1142/S1793830916500488
- Publisher
- World Scientific Publishing
- Resource Type
- journal article
- Date
- 2016
- Description
- For a simple graph G = (V,E) and for a pair of vertices u, v ∈ V , we say that a vertex w ∈ V resolves u and v if the shortest path from w to u is of a different length than the shortest path from w to v. A set of vertices R ⊆ V is a resolving set if for every pair of vertices u and v in G, there exists a vertex w ∈ R that resolves u and v. The minimum weight resolving set problem is to find a resolving set M for a weighted graph G such that Σv∈ M w(v) is minimum, where w(v) is the weight of vertex v. In this paper, we explore the possible solutions of this problem for grid graphs Pn⎕Pm where 3 ≤ n ≤ m. We give a complete characterization of solutions whose cardinalities are 2 or 3, and show that the maximum cardinality of a solution is 2n − 2. We show that the grid has the property that given a landmark set, we only need to investigate whether or not all pairs of vertices that share common neighbors are resolved to determine if the whole graph is resolved. We use this result to provide a characterization of a class of minimals whose cardinalities range from 4 to 2n−2 and show that the number of such minimals is Ω(2n).
- Subject
- weighted metric dimension; resolving sets; grid graphs
- Identifier
- http://hdl.handle.net/1959.13/1345845
- Identifier
- uon:29729
- Identifier
- ISSN:1793-8309
- Language
- eng
- Reviewed
- Hits: 1210
- Visitors: 1188
- Downloads: 0
| Thumbnail | File | Description | Size | Format |
|---|